//乘积最大子数组

package Leetcode;

import java.util.Arrays;

class Solution152_1 {
    public int maxProduct(int[] nums) {
        if (nums.length == 0)
            return 0;
        if (nums.length == 1)
            return nums[0];

        int prev = 0; // 前一个0的位置
        int max = 0; // 记录最终最大值
        for (int i = 0; i <= nums.length; i++) {
            if (i == nums.length || nums[i] == 0) {
                int idex = maxProductWithoutZero(Arrays.copyOfRange(nums, prev, i));
                max = max > idex ? max : idex;
                prev = i + 1;
            }
        }
        return max;
    }

    public int maxProductWithoutZero(int[] nums) {
        if (nums.length == 0)
            return 0;
        if (nums.length == 1)
            return nums[0];

        int prod = 1;// 求整个数组的积
        for (int i = 0; i < nums.length; i++)
            prod *= nums[i];

        if (prod > 0) // 如果大于0直接返回，表示该非零子数组能得到的最大乘积
            return prod;

        int headProd = 1; // 从头到第一个负数的乘积
        int backProd = 1; // 从尾到第一个负数的乘积
        for (int i = 0; i < nums.length; i++) {
            headProd *= nums[i];
            if (nums[i] < 0)
                break;
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            backProd *= nums[i];
            if (nums[i] < 0)
                break;
        }

        return headProd > backProd ? prod / headProd : prod / backProd;
    }
}

class Solution152_2 {
    public int maxProduct(int[] nums) {
        int[] dpMax = new int[nums.length]; // 表示以i结尾的子数组的乘积最大值
        int[] dpMin = new int[nums.length]; // 表示以i结尾的子数组的乘积最小值
        int reuslt = nums[0];
        // 初始化
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        // 状态转移方程为：
        // dpMax[i] = max(dpMax[i-1]*nums[i],dpMin[i-1]*nums[i],nums[i])
        // dpMin[i] = min(dpMax[i-1]*nums[i],dpMin[i-1]*nums[i],nums[i])
        for (int i = 1; i < nums.length; i++) {
            dpMax[i] = Math.max(Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i]);
            dpMin[i] = Math.min(Math.min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i]);
            reuslt = reuslt > dpMax[i] ? reuslt : dpMax[i];
        }
        return reuslt;
    }
}